/*
day106
2019.12.12
*/
#include<vector>
#include<iostream>
using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) 
	{
		vector<int> vec;
		int size=numbers.size();
        for(int i=0;i<size;i++)
        {
        	int tem=numbers[i];
    
        	int j=find(numbers,i+1,size-1,target-tem);
        	
        	if(j!=-1)
        	{
        		vec.push_back(i+1);
        		vec.push_back(j+1);
        		break;
			}
		}
		return vec;
    }
    
    int find(vector<int>& numbers,int begin,int end,int target)
    {
    	if(begin>end) return -1;
    	
    	int left=begin,right=end;
    	int mid=(begin+end)/2;
    	
    	if(numbers[mid]==target) return mid;
    	
    	else if( target > numbers[mid] )
    	{
    		return find(numbers,mid+1,right,target);
		}
		else{
			return find(numbers,left,mid-1,target);
		}
	}
};


int main()
{
	vector<int> numbers={5,25,75};
	int target=100;
	Solution s;
	vector<int> vec=s.twoSum(numbers,target);
	for(int i=0;i<vec.size();i++)
	{
		cout<<vec[i]<<endl;
	}

//	cout<<s.find(numbers,0,numbers.size()-1,75)<<endl;
	
	return 0;
}
